package com.leetcode.HW;

/**
 * @author lzf
 * @create 2024/12/07
 * @description TODO
 */

/**
 * 一个歌手准备从A城去B城参加演出。
 *
 * 按照合同，他必须在 T 天内赶到
 * 歌手途经 N 座城市
 * 歌手不能往回走
 * 每两座城市之间需要的天数都可以提前获知。
 * 歌手在每座城市都可以在路边卖唱赚钱。经过调研，歌手提前获知了每座城市卖唱的收入预期：如果在一座城市第一天卖唱可以赚M，后续每天的收入会减少D（第二天赚的钱是 M - D，第三天是 M - 2D ...）。如果收入减少到 0 就不会再少了。
 * 歌手到达后的第二天才能开始卖唱。如果今天卖过唱，第二天才能出发。
 * 贪心的歌手最多可以赚多少钱？
 */

/**
 * 输入描述
 * 第一行两个数字 T 和 N，中间用空格隔开。
 *
 * T 代表总天数，0 < T < 1000
 * N 代表路上经过 N 座城市，0 < N < 100
 * 第二行 N+1 个数字，中间用空格隔开。代表每两座城市之间耗费的时间。
 *
 * 其总和 ≤ T。
 * 接下来 N 行，每行两个数字 M 和 D，中间用空格隔开。代表每个城市的输入预期。
 *
 * 0 < M < 1000
 * 0 < D < 100
 * 输出描述
 * 一个数字。代表歌手最多可以赚多少钱。以回车结束。
 */

import java.util.Arrays;
import java.util.Scanner;

/**
 * 比如经过两个城市c1 c2，那么就有 A -> c1 -> c2 -> B，所以有输入的第二行 N+1个数字，代表每两座城市之间耗费的时间（天数）。
 * 路途消耗的天数不能赚钱，所以除去在路上的天数，剩下的天数remainDay都可以赚钱
 * 一开始，remainDay每一天初始化为0，表示每一天赚0元。 result数组
 * 每经过一个城市，计算在该城市在剩下的每一天能赚多少，city数组
 * 在result数组和city数组中，一共取remainDay个最大的值，就是到达该城市所能赚到的最多的钱。
 * 再重新保存在result中。
 * 比如，remainDay = 6天。目前的result：120 100 80 90 80 70
 * 当前的city：150 140 130 120 110 100
 * 那么更新完，result应该是：150 140 130 120 120 110，表示在前面的城市中，呆一天，然后在当前city呆5天。这样赚最多。
 */
public class HW贪心歌手 {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int totalDay = input.nextInt();
        int size = input.nextInt();
        int S = 0;
        for (int i = 0; i <= size; i++) {
            S += input.nextInt();
        }
        int remainDay = totalDay - S;
        // 创建3个数组即可
        int[] result = new int[remainDay];
        int[] temp = new int[remainDay];
        int[] city = new int[remainDay];
        for (int i = 0; i < size; i++) {
            int max = input.nextInt();
            int step = input.nextInt();
            city[0] = max;
            for (int j = 1; j < remainDay;j++) {
                int cur = city[j - 1] - step;
                if (cur < 0) {
                    // 最小是0
                    city[j] = 0;
                    break;
                } else {
                    city[j] = cur;
                }
            }
            // 每次更新，就是result和city的比较，但是结果需要保存在result，所以需要一个temp去接收保存前的result，那么temp就是需要跟city比较的数组
            int[] t = temp;
            temp = result;
            result = t;
            updateResult(result, city, temp, remainDay);
        }
        System.out.println(Arrays.stream(result).sum());
    }
    public static void updateResult(int[] result, int[] city, int[] temp, int remainDay) {
        int t = 0;
        int c = 0;
        for (int i = 0; i < remainDay; i++) {
            // 不用管越界，因为每个数组的长度是一样的
            if (temp[t] > city[c]) {
                result[i] = temp[t];
                t++;
            } else {
                result[i] = city[c];
                c++;
            }
        }
    }
}
